Software is said to exhibit scalable parallelism if it can make use of additional processors to solve larger problems,
i.e. this term refers to software for which
Gustafson's law
In computer architecture, Gustafson's law (or Gustafson–Barsis's law) gives the speedup in the execution time of a task that theoretically gains from parallel computing, using a hypothetical run of ''the task'' on a single-core machine as the ba ...
holds.
Consider a program whose execution time is dominated by one or more loops,
each of that updates every element of an array ---
for example, the following
finite difference
A finite difference is a mathematical expression of the form . If a finite difference is divided by , one gets a difference quotient. The approximation of derivatives by finite differences plays a central role in finite difference methods for t ...
heat equation
In mathematics and physics, the heat equation is a certain partial differential equation. Solutions of the heat equation are sometimes known as caloric functions. The theory of the heat equation was first developed by Joseph Fourier in 1822 for t ...
stencil calculation:
for t := 0 to T do
for i := 1 to N-1 do
new(i) := (A(i-1) + A(i) + A(i) + A(i+1)) * .25
// explicit forward-difference with R = 0.25
end
for i := 1 to N-1 do
A(i) := new(i)
end
end
In the above code, we can execute all iterations of each "i" loop concurrently,
i.e., turn each into a
parallel loop.
In such cases,
it is often possible to make effective use of twice as many processors for a problem of array size 2N
as for a problem of array size N.
As in this example, scalable parallelism is typically a form of
data parallelism
Data parallelism is parallelization across multiple processors in parallel computing environments. It focuses on distributing the data across different nodes, which operate on the data in parallel. It can be applied on regular data structures like ...
.
This form of parallelism is often the target of
automatic parallelization
Automatic may refer to:
Music Bands
* Automatic (band), Australian rock band
* Automatic (American band), American rock band
* The Automatic, a Welsh alternative rock band
Albums
* Automatic (Jack Bruce album), ''Automatic'' (Jack Bruce a ...
of
loops.
Distributed computing systems and
non-uniform memory access
Non-uniform memory access (NUMA) is a computer memory design used in multiprocessing, where the memory access time depends on the memory location relative to the processor. Under NUMA, a processor can access its own local memory faster than non- ...
architectures
are typically the most easily scaled to large numbers of processors,
and thus would seem a natural target for software that exhibits scalable parallelism.
However, applications with scalable parallelism may not have parallelism of
sufficiently
coarse grain
to run effectively on such systems (unless the software is
embarrassingly parallel
In parallel computing, an embarrassingly parallel workload or problem (also called embarrassingly parallelizable, perfectly parallel, delightfully parallel or pleasingly parallel) is one where little or no effort is needed to separate the problem i ...
).
In our example above, the second "i" loop is embarrassingly parallel,
but in the first loop each iteration requires results produced in several prior iterations.
Thus, for the first loop, parallelization may involve extensive communication or synchronization among processors,
and thus only result in a net speedup if such interactions have very low overhead,
or if the code can be transformed to resolve this issue (i.e., by combined
scalable locality/scalable parallelism optimization
).
Languages
*
Ateji PX an extension of Java making Scalable Parallelism possible on the Java Virtual Machine (JVM)
*
BMDFM Binary Modular DataFlow Machine
*
SequenceL is a general purpose functional programming language, whose primary design objectives are performance on multicore hardware, ease of programming, and code clarity/readability
References
External links
* {{Cite web, title=Demystify Scalable Parallelism with Intel Threading Building Block's Generic Parallel Algorithms , url=http://www.devx.com/cplus/Article/32935
Analysis of parallel algorithms
Articles with example pseudocode